import java.util.Arrays;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String s="[";
        Solution w=new Solution();
        boolean b=w.isValid(s);
        System.out.println(b);
        int[] el=new int[10];
        el=Arrays.copyOf(el,2*el.length);
    }
}
class MinStack {

    public MinStack() {
        int[] el = new int[1000];
        int numsize = 0;
    }

    // private void grow(){
    //     this.el=Arrays.copyof(el,2*el.lenth);
    // }

    public void push(int val) {
        // if (el.lenth == numsize) {
        //     grow();
        // }
        el[numsize] = val;
        numsize++;
    }

    public void pop() {
        if (empty)
            return -1;
        return el[--numsize];
    }

    public int top() {
        return el[numsize - 1];

    }

    private boolean empty() {
        return numsize == 0;
    }

    public int getMin() {
        int num = 0;
        for (int i = 0; i < numsize; i++) {
            if (el[i] < num)
                num = el[i];
        }
        return num;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
    class Solution {
        public boolean isValid(String s) {
            Stack<Character> st = new Stack();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == '(' || ch == '[' || ch == '{') {
                    st.push(ch);
                } else {
                    if (st.empty()) {
                        return false;
                    }
                    char ch2 =st.peek();
                    if (ch2 == '(' && ch == ')' || ch2 == '[' &&
                            ch == ']' || ch2 == '{' && ch == '}') {
                        st.pop();

                    }else{
                        return false;
                    }

                }

            }

            return true;
        }
    }class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[10];
    }

    public void push(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[usedSize++] = val;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    public int pop() {
        if (isEmpty())
            return -1;
        int val = elem[usedSize - 1];
        usedSize--;
        return val;

    }

    //获取栈顶元素 但是不删除
    public int peek() {
        if (isEmpty())
            return -1;
        return elem[usedSize - 1];
    }

    public boolean isEmpty() {
        if (usedSize == 0)
            return true;
        else
            return false;

    }
}